package com.scqzy.shengchunqiang.sword2offer.day07;

import com.scqzy.shengchunqiang.structure.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;

/**
 * @Description: 剑指 Offer 26. 树的子结构
 * @Author 盛春强
 * @Date 2021/8/14 19:32
 */
public class IsSubStructure {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (Objects.isNull(A) || Objects.isNull(B)) {
            return false;
        }
        return isPartTree1(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isPartTree(TreeNode p, TreeNode q) {
        if (Objects.isNull(q)) {
            return true;
        }
        if (Objects.isNull(p)) {
            return false;
        }
        return p.val == q.val && isPartTree(p.left, q.left) && isPartTree(p.right, q.right);
    }

    public boolean isPartTree1(TreeNode p, TreeNode q) {
        if (Objects.isNull(q)) {
            return true;
        }
        if (Objects.isNull(p)) {
            return false;
        }
        Deque<TreeNode> pDeque = new ArrayDeque<>();
        Deque<TreeNode> qDeque = new ArrayDeque<>();
        pDeque.offer(p);
        qDeque.offer(q);
        while (!pDeque.isEmpty()) {
            TreeNode pPoll = pDeque.poll();
            TreeNode qPoll = qDeque.poll();
            if (pPoll.val != qPoll.val) {
                return false;
            }
            if (Objects.isNull(pPoll.left) && Objects.nonNull(qPoll.left)) {
                return false;
            }
            if (Objects.isNull(pPoll.right) && Objects.nonNull(qPoll.right)) {
                return false;
            }
            if (Objects.nonNull(pPoll.left) && Objects.nonNull(qPoll.left)) {
                pDeque.offer(pPoll.left);
                qDeque.offer(qPoll.left);
            }
            if (Objects.nonNull(pPoll.right) && Objects.nonNull(qPoll.right)) {
                pDeque.offer(pPoll.right);
                qDeque.offer(qPoll.right);
            }
        }
        return qDeque.isEmpty();
    }

    public static void main(String[] args) {
        TreeNode a = TreeNode.array2Treenode(new int[]{10, 12, 6, 8, 3, 11});
        TreeNode b = TreeNode.array2Treenode(new int[]{10, 12, 6, 8});
        IsSubStructure isSubStructure = new IsSubStructure();
        boolean isSubStructureSubStructure = isSubStructure.isSubStructure(a, b);
        System.out.println(isSubStructureSubStructure);

    }
}
